package com.sheepone.util.structure.tree.binary;

import com.sheepone.util.structure.Container;
import com.sheepone.util.structure.node.BinaryTreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Miss.杨
 * @description
 * @since 2024/5/16 - 18:55
 */
public class BranchedBinaryTree<V> extends Container implements BinaryTree<V> {
    protected BinaryTreeNode<V> root;

    @Override
    public void clear() {

    }

    @Override
    @SuppressWarnings("all")
    public List<List<V>> layerTransfer() {
        List<List<V>> transfer = new ArrayList<>();
        if (root != null) {
            Queue<BinaryTreeNode<V>> queue = new LinkedList<>();
            queue.offer(root);
            int size;
            BinaryTreeNode<V> node;
            ArrayList<V> list;
            while (!queue.isEmpty()) {
                size = queue.size();
                list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
                    node = queue.poll();
                    list.add(node.getValue());
                    if (node.getLeft() != null) {
                        queue.offer(node.getLeft());
                    }
                    if (node.getRight() != null) {
                        queue.offer(node.getRight());
                    }
                }
                transfer.add(list);
            }
        }
        return transfer;
    }

    @Override
    public List<V> preOrderTransfer() {
        return null;
    }

    @Override
    public List<V> inOrderTransfer() {
        return null;
    }

    @Override
    public List<V> postOrderTransfer() {
        return null;
    }

    @Override
    public boolean isSymmetrical() {
        return isSymmetric(root.getLeft(), root.getRight());
    }

    private boolean isSymmetric(BinaryTreeNode<V> left, BinaryTreeNode<V> right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return left.getValue().equals(right.getValue()) && isSymmetric(left.getLeft(), right.getRight()) && isSymmetric(left.getRight(), right.getLeft());
    }

    @Override
    public int layers() {
        return 0;
    }

    /**
     * 【层序遍历】获取二叉树的最大深度
     *
     * @return
     */
    @Override
    @SuppressWarnings("all")
    public int maxDepth() {
        int deepth = 0;
        if (root != null) {
            Queue<BinaryTreeNode<V>> queue = new LinkedList<>();
            queue.offer(root);
            int size;
            BinaryTreeNode<V> node;
            while (!queue.isEmpty()) {
                deepth++;
                size = queue.size();
                for (int i = 0; i < size; i++) {
                    node = queue.poll();
                    if (node.getLeft() != null) {
                        queue.offer(node.getLeft());
                    }
                    if (node.getRight() != null) {
                        queue.offer(node.getRight());
                    }
                }
            }
        }
        return deepth;
    }

    @Override
    public int minDepth() {
        return 0;
    }

    @Override
    public BinaryTree<V> reverse() {
        invertTree(root);
        return this;
    }

    private void invertTree(BinaryTreeNode<V> root) {
        if (root == null) {
            return;
        }
        BinaryTreeNode<V> node = root.getLeft();
        root.setLeft(root.getRight());
        root.setRight(node);
        invertTree(root.getLeft());
        invertTree(root.getRight());
    }

    @Override
//    @SuppressWarnings("all")
    public boolean equals(Object obj) {
        if (obj instanceof BranchedBinaryTree tree) {
            return isSameTree(root, tree.root);
        }
        // todo 是否需要重写hashcode方法
        return false;
    }

    /**
     * 【递归】判断两棵树是否相同
     *
     * @param p
     * @param q
     * @return
     */
    private boolean isSameTree(BinaryTreeNode<V> p, BinaryTreeNode<V> q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.getValue().equals(q.getValue())) {
            return isSameTree(p.getLeft(), q.getLeft()) && isSameTree(p.getRight(), q.getRight());
        }
        return false;
    }
}
